
%%%%%%%%%%%%%%%%%%%%%%% file typeinst.tex %%%%%%%%%%%%%%%%%%%%%%%%%
%
% This is the LaTeX source for the instructions to authors using
% the LaTeX document class 'llncs.cls' for contributions to
% the Lecture Notes in Computer Sciences series.
% http://www.springer.com/lncs       Springer Heidelberg 2006/05/04
%
% It may be used as a template for your own input - copy it
% to a new file with a new name and use it as the basis
% for your article.
%
% NB: the document class 'llncs' has its own and detailed documentation, see
% ftp://ftp.springer.de/data/pubftp/pub/tex/latex/llncs/latex2e/llncsdoc.pdf
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\documentclass[runningheads,a4paper]{llncs}

\usepackage{amssymb}
\setcounter{tocdepth}{3}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{array}
\usepackage{subfigure}
%\usepackage{url}
%\urldef{\mailsa}\path|{alfred.hofmann, ursula.barth, ingrid.haas, frank.holzwarth,|
%\urldef{\mailsb}\path|anna.kramer, leonie.kunz, christine.reiss, nicole.sator,|
%\urldef{\mailsc}\path|erika.siebert-cole, peter.strasser, lncs}@springer.com|    
\newcommand{\keywords}[1]{\par\addvspace\baselineskip
\noindent\keywordname\enspace\ignorespaces#1}
\clubpenalty = 10000
\widowpenalty = 10000
\displaywidowpenalty = 10000
					
\usepackage[T1]{fontenc}
\usepackage{ae,aecompl}
\input{commands.tex}
\input{commands1.tex}
\usepackage{epsfig}
\linespread{0.95}
\newtheorem{name}{Printed output}
\newcommand{\choreos}[0]{\textit{CHOReOS}~}
\usepackage{listings}


\lstset{language=Python,
        morekeywords=[1]{yield}
}  

% pre-load the language
\lstloadlanguages{Python} %  comma separated list of languages


% Style
% ~~~~~
% 
% Typeface settings::

\lstset{
  basicstyle=\tt\scriptsize,           % print whole listing in tt
  % basicstyle=\ttfamily\small,   % and, maybe small    
  keywordstyle=\bf,
  % identifierstyle=\slshape,     % object names
  commentstyle=\itshape, % italic comments
  stringstyle=\slshape,           % strings
}

\begin{document}

\mainmatter  % start of an individual contribution

% first the title is needed
\title{QoS Analysis in Heterogeneous Choreography Interactions}

% a short form should be given in case it is too long for the running head
\titlerunning{QoS Analysis in Heterogeneous Choreography Interactions}

% the name(s) of the author(s) follow(s) next
%
% NB: Chinese authors should write their first names(s) in front of
% their surnames. This ensures that the names appear correctly in
% the running heads and the author index.
%
\author{Ajay Kattepur, Nikolaos Georgantas \& Val\'erie Issarny%
%\thanks{Please note that the LNCS Editorial assumes that all authors have used
%the western naming convention, with given names preceding surnames. This determines
%the structure of the names in the running heads and the author index.}%
}
%
\authorrunning{QoS Analysis in Heterogeneous Choreography Interactions}
% (feature abused for this document to repeat the title also on left hand pages)

% the affiliations are given next; don't give your e-mail address
% unless you accept that it will be published
\institute{Equipe ARLES, Inria Paris-Rocquencourt, France.\\
$email$: firstname.lastname@inria.fr}

%
% NB: a more complex sample for affiliations and the mapping to the
% corresponding authors can be found in the file "llncs.dem"
% (search for the string "\mainmatter" where a contribution starts).
% "llncs.dem" accompanies the document class "llncs.cls".
%

\toctitle{Lecture Notes in Computer Science}
\tocauthor{Authors' Instructions}
\maketitle


\begin{abstract}
With an increasing number of services and devices interacting in a decentralized manner, \emph{choreographies} are an active
area of investigation. The heterogeneous nature of interacting systems leads to choreographies
that may not only include conventional services, but also sensor-actuator networks, databases and service feeds. Their middleware behavior within choreographies
is captured through abstract interaction paradigms such as \emph{client-service}, \emph{publish-subscribe} and \emph{tuple space}. In this paper, we study these heterogeneous interaction paradigms, connected through an \emph{eXtensible Service Bus} proposed in the \choreos project. As the functioning of such choreographies is dependent on the Quality of Service (QoS) performance of participating entities, an intricate analysis of interaction paradigms and their effect on QoS metrics is needed. We study the composition of QoS metrics in heterogeneous choreographies, and the subsequent tradeoffs. This produces interesting insights such as selection of a particular system and its middleware during design time or end-to-end QoS expectation/guarantees during runtime. Non-parametric hypothesis tests are applied to systems, where QoS dependent middleware may be replaced at runtime to prevent deterioration in performance.
\keywords{Heterogeneous Choreographies, Quality of Service, Interaction Paradigms, Middleware Connectors.}
\end{abstract}


\section{Introduction}

\emph{Choreographies}, unlike centrally controlled orchestrations, involve a de-centralized service composition framework where only the participants' functionality and associated message passing are described \cite{barker}. Service Oriented Architectures (SOA) allow choreography components to interact via standard interfaces, with the enterprise service bus (ESB) \cite{esb} providing a common middleware protocol to convey the messaging interactions. However, these are principally based on the \emph{client-service} interaction paradigm, as, for instance, with RESTful services \cite{restful}.

Heterogeneous choreographies that involve conventional services, sensor networks and data feeds, such as those seen in the \emph{Internet of Things} \cite{iot1}, require additional interaction paradigm interoperability. Heterogeneous devices are handled at the middleware level with varied interactions, data structures and communication protocols made interoperable. In particular, platforms such as REST \cite{restful} based \emph{client-service} interactions, \emph{publish-subscribe} based Java Messaging Service \cite{JMS} or JavaSpaces \cite{javaspaces} for \emph{tuple space} are made interoperable through \emph{middleware protocol converters}. 

Studies that characterize the Quality of Service (QoS) in web services orchestrations have conventionally been done at the application level; heterogeneous choreographies consisting of services and sensor networks require further QoS analysis of paradigms, unless they can rely on QoS aware middleware \cite{qos_middleware}. An intricate analysis of QoS at the abstract level of interaction paradigms, in addition to the application level, would enable analysis of QoS-aware heterogeneous choreographies. 

In this paper\footnote{\scriptsize{This work has been partially supported by the European Union's 7th Framework Programme FP7/ 2007-2013 under grant agreement number 257178 (project CHOReOS, \url{http://www.choreos.eu}).}}, we use the \emph{eXtensible Service Bus (XSB)} proposed by the \choreos project \cite{choreos,esocc13} in order to deal with the heterogeneous aspects of choreographies. The common protocol of XSB preserves the interaction paradigms of the individual components, while still allowing interoperability. It supports interoperability among the three aforementioned, widely used, middleware paradigms: \emph{client-service}, \emph{publish-subscribe} and \emph{tuple space}.

We enhance the middleware paradigms that are employed inside heterogeneous choreographies with QoS composition frameworks. Consolidating QoS composition in choreographies with awareness of the underlying middleware paradigms provides improved insights over application level QoS. By fine-grained analysis of interactions, we evaluate the performance of choreography participants in relation to heterogeneous paradigms. This methodology enables: 1) Design-time selection of interaction paradigms to match required functional and QoS goals, and 2) Runtime analysis of composed choreographies to prevent deterioration of end-to-end QoS of participants. Interesting facets include the use of non-parametric Kolmogorov-Smirnov hypothesis testing to replace an interaction paradigm with another, when abstracted with a particular QoS metric.

The rest of the paper is organized as follows. An overview of heterogeneous interaction paradigms and XSB is provided in Section \ref{sdjkfsdjknbjk}. The QoS domains, metrics and algebra for composition are studied in Section \ref{wdklghskdjlhfialhlk}. The methodology of measuring and propagating QoS increments across various domains are analyzed in Section \ref{kldakljasdfjk}. The results of our analysis through experiments are presented in Section \ref{sdkgjlksdjgklsjglsjd}, which includes an analysis of tradeoffs and interaction substitution. This is followed by related work and conclusions in Sections \ref{fsdmlkjflksdjk} and \ref{dfjsudhfiuwshhio}, respectively. 


\section{Interconnecting Heterogeneous Interaction Paradigms}
\label{sdjkfsdjknbjk}
\noindent In this section, we briefly describe the three interaction paradigms that may be abstractly applied within our QoS analysis framework. 
The functional semantics of these paradigms are abstracted into a set of corresponding \emph{middleware connectors} proposed by the \choreos project.
After that, we provide an overview of the \emph{eXtensible Service Bus (XSB) connector}, which ensures interoperability across these connectors and the represented paradigms.

\subsection{Interaction Paradigm Connectors}
In order to let choreographies include services (typically, client-service interactions), service feeds (publish-subscribe), and sensor-actuator networks (shared tuple spaces), it is a requirement to allow heterogeneity. We briefly review in the following the relevant interaction paradigms \cite{esocc13}, and discuss the Application Programming Interfaces (APIs) of corresponding connectors \cite{choreos}. These APIs are depicted in Table \ref{Pdeskjfhksjgdjhg}.
Their primitives and arguments are provided, with $\uparrow$ representing an \texttt{out} or \texttt{in-out} argument of a primitive.

	\begin{table}[t]
		\vspace{-0.05in}
		\centering
		{\scriptsize
	\begin{tabular}{|p{2.2cm} |p{2.2cm} | p{7.7cm}|}
	\hline
	\textbf{Interaction} & \textbf{Primitives}&\textbf{Arguments}\\ \hline
  Client-Service & 
	\texttt{send} & \texttt{destination, operation, message}\\
	&\texttt{receive\_sync} & $\uparrow$\texttt{source,} $\uparrow$\texttt{operation,} $\uparrow$\texttt{message, timeout}\\
	&\texttt{receive\_async} & \texttt{source,} \texttt{operation,} $\uparrow$\texttt{callback(source, operation, message),} $\uparrow$\texttt{handle}\\
	&\texttt{end\_receive\_async} & \texttt{handle}\\ 
	&\texttt{invoke\_sync} & \texttt{destination, operation, in\_msg,} $\uparrow$\texttt{out\_msg, timeout}\\
	&\texttt{invoke\_async} & \texttt{destination, operation, in\_msg,} $\uparrow$\texttt{callback(out\_msg),} $\uparrow$\texttt{handle}\\
	\hline
	
	Publish-Subscribe &	\texttt{publish} & \texttt{broker, filter, event, lease}\\
	&\texttt{subscribe} & \texttt{broker, $\uparrow$filter, $\uparrow$handle}\\
	&\texttt{get\_next} & \texttt{handle, $\uparrow$event, timeout}\\
	&\texttt{listen} & \texttt{handle, $\uparrow$callback(event)}\\
	&\texttt{end\_listen} & \texttt{handle}\\
	&\texttt{unsubscribe} & \texttt{handle}\\ \hline

	Tuple Space & \texttt{out} & \texttt{tspace, extent, template, tuple, lease} \\
	&\texttt{take} & \texttt{tspace, extent, template, policy, $\uparrow$tuple, timeout}\\
	&\texttt{read} & \texttt{tspace, extent, template, policy, $\uparrow$tuple, timeout}\\
	&\texttt{register} & \texttt{tspace, extent, template, $\uparrow$callback(), $\uparrow$handle}\\
  &\texttt{unregister} & \texttt{handle}\\ \hline
	\end{tabular}}
	\vspace{0.05in}
	\caption{APIs of Interaction Paradigms.}
	\label{Pdeskjfhksjgdjhg}
	\vspace{-0.4in}
	\end{table}
	
\begin{itemize}
	\item \emph{Client-Service (CS)} - Commonly used paradigm for web services. The client may send a message with \texttt{send}; the receiving service blocks further execution until synchronization or \texttt{timeout}, with a \texttt{receive\_sync}. Alternatively, asynchronous reception can be set up with \texttt{receive\_async}; then, a \texttt{callback} is triggered by the middleware when a message arrives. The two-way request-response invocation procedure is further captured by the \texttt{invoke\_sync} and \texttt{invoke\_async} primitives. CS represents tight \emph{space coupling}, with the client and service having knowledge of each other. There is also tight \emph{time coupling}, with service availability being crucial for successful message passing.
		\item \emph{Publish-Subscribe (PS)} - Commonly used paradigm for content broadcasting/feeds. Multiple peers interact using an intermediate \emph{broker} service. Publishers \texttt{publish} events that may be forwarded to peers via the broker until a \texttt{lease} period. Filtering (\texttt{filter}) of messages may be done with respect to subscriptions (\texttt{subscribe}) of the peers. Besides synchronous reception (\texttt{get\_next} with \texttt{timeout}) of an event, asynchronous reception of multiple events is procured via \texttt{listen} and \texttt{callback}. PS allows \emph{space decoupling}, as the peers need not know each other. Additionally, \emph{time decoupling} is possible, with the disconnected peers receiving updates synchronously or asynchronously when reconnected to the broker. 
	\item \emph{Tuple Space (TS)} - Commonly used for shared data with multiple read/write users. Peers interact with a \emph{data space}, with participants having write (\texttt{out}), \texttt{read} and data removal (\texttt{take}) access. The peers can retrieve data whose value matches a \texttt{tuple} pattern (\texttt{template}), either synchronously with a \texttt{timeout} or asynchronously via \texttt{register} and \texttt{callback}. A peer may connect to the space at any time and procure data before the \texttt{lease} period. TS enables both space and time decoupling between interacting peers. 

\end{itemize}
	
%These interaction paradigms are represented in Fig. \ref{dfl;jglksjdfls}.
%
%\begin{figure}[ht]
%\centering
%\includegraphics[height=14cm]{interaction.eps}
%\caption{Message Interaction Paradigms}
%\label{dfl;jglksjdfls}
%\end{figure}

\subsection{eXtensible Service Bus (XSB)}

\choreos \cite{choreos} uses the following abstractions to deal with large scale choreographies that connect heterogeneous participants:
\begin{itemize}
	\item \emph{Components}: The heterogeneity of services and devices encountered are modeled as \emph{service interface abstractions}, which
represent groups of alternative services that provide similar functionalities through varied interfaces. 
\item \emph{Connectors}: This definition relates to the introduction of a new multi-paradigm \emph{eXtensible Service Bus (XSB) connector},
which allows components to interoperate even if they are based on heterogeneous interaction
paradigms. XSB extends the conventional ESB system integration paradigm \cite{esocc13}. 
\item \emph{Coordination Delegates}: These are used to enforce the realizability of choreographies
despite the autonomy of the composed services. They ensure that the choreography specifications, such as message ordering integrity, are adhered to by the
participating entities.
\end{itemize}

\begin{figure}[h]
\vspace{-0.3in}
	\centering
		\includegraphics[height=6.5cm]{GA_model.eps}
	\caption{\choreos Choreography Model.}
	\vspace{-0.1in}
	\label{fig:CHOReOS}
	\vspace{-0.1in}
\end{figure}

The generic representation of the \choreos model is shown in Fig. \ref{fig:CHOReOS}, with services/devices represented by \emph{components} abstracting their functional behavior. At the choreography level, the \emph{coordination delegates} wrap such services and adapt their roles to message passing specifications. The \emph{XSB connector} ensures interoperability across a host of middleware protocols (following the CS, PS, TS paradigms). Note that there are multiple types of components that may participate: \emph{Atomic/Composite Services} (CS requests-responses); \emph{Data Feed Services} (they publish PS events, which are then passed to subscribers); \emph{Sensor Actuator Networks} (TS-based interaction).

The semantics of the XSB connector is elicited as the \textit{greatest common denominator} of the semantics of the CS, PS and TS connectors.
As the latter semantics are incompatible in certain aspects, some enforcement by the applications employing the heterogeneous connectors may be necessary.
For example, the two-way, time-coupled, CS interaction has no equivalent in the PS and TS paradigms. In this case, the PS and TS applications interacting with a CS application will have to complement the semantics of their underlying connectors with the lacking behavior (e.g., ensure that a PS peer receiving a published event will respond by publishing a correlated event that will be received by the initial publishing peer).
Hence, the XSB connector can abstractly represent any of the three CS, PS and TS connectors. The XSB API is depicted in Table \ref{kjbvfnjkghekhxdjvkjh}.
It employs primitives such as \texttt{post} and \texttt{get} to abstract CS (\texttt{send, receive}), PS (\texttt{publish, get\_next}), and TS (\texttt{out, take/read}) interactions.  
The \texttt{data} element can represent a CS \texttt{message}, PS \texttt{event} or TS \texttt{tuple}.
The \texttt{scope} argument is used to unify space coupling (addressing mechanisms) across CS, PS and TS.
Two-way interaction is enabled with the \texttt{post-get} primitive.
Additionally, XSB is the \emph{common bus protocol} employed for the interconnection of CS, PS and TS systems, as seen in Fig. \ref{fig:CHOReOS}.
Finally, XSB represents also the \emph{end-to-end interaction protocol} among such interconnected systems. 
	
		\begin{table}[t]
		\vspace{-0.05in}
	\centering
		{\scriptsize
	\begin{tabular}{|p{2.5cm} | p{7cm}|}
	\hline
	\textbf{Primitives}&\textbf{Arguments}\\\hline
	\texttt{post} & \texttt{scope, data}\\
	\texttt{get\_sync}& \texttt{$\uparrow$scope, $\uparrow$data, timeout}\\
	\texttt{get\_async}& \texttt{scope, $\uparrow$callback(scope, data), $\uparrow$handle}\\
	\texttt{end\_get\_async}&\texttt{handle}\\
	\texttt{post\_get\_sync}&\texttt{scope, in\_data, $\uparrow$out\_data, timeout}\\
  \texttt{post\_get\_async}&\texttt{scope, in\_data, $\uparrow$callback(out\_data), $\uparrow$handle}\\	\hline
	\end{tabular}}
	\vspace{0.05in}
	\caption{XSB connector API.}
	\label{kjbvfnjkghekhxdjvkjh}
				\vspace{-0.35in}
	\end{table}

%\begin{figure}[h]
%\vspace{-0.2in}
	%\centering
		%\includegraphics[height=6cm]{GA_model.eps}
	%\caption{Connecting Heterogeneous paradigms across the connector.}
	%\label{kdjfbakjsfhfkjskj}
	%\vspace{-0.4in}
%\end{figure}
	
	
\section{Modeling Quality of Service}
\label{wdklghskdjlhfialhlk}
While conventional middleware paradigms deal with aspects of heterogeneity and functional interoperability, choreographies relate to additional non-functional aspects during design/runtime, which require analysis. This specifically involves constraints on QoS performance of individual participants and their side-effects on choreography enaction. QoS metrics being probabilistic and multi-dimensional, accurate analysis of increments and composition rules are crucial. In this section, the QoS domains that are of interest for interactions and the corresponding algebra for their composition are analyzed. 

\subsection{QoS Domains}
We review the basic domains of QoS that require analysis for heterogeneous choreography interactions. We identify three basic domains \cite{pubsub_QoS}:

\begin{itemize}
\item $\delta$:~\emph{Timeliness} incorporates aspects such as latency and reliable message delivery. For the case of client-service interactions, timeliness concerns one-way message or two-way request-response latency. In case of publish-subscribe, the latency between publication to a broker and subsequent coupled or decoupled delivery to peers is examined. With tuple space, the latency between writing to a tuple and coupled or decoupled access to the data is analyzed.
\item $\mathcal{S}$:~\emph{Security/Data Integrity} incorporates the trustworthiness of the interaction paradigms with respect to the confidentiality of information. This especially holds in publish-subscribe systems, where there is an intermediate broker, or tuple spaces, where there is an intermediate space and multiple peers have access to the same data. For example, a peer in the tuple space may remove and modify the data before they are procured by the other peers.
\item $\lambda$:~\emph{Resource Efficiency} incorporates multiple aspects, such as efficiency in bandwidth usage and protocol message passing. In the case of publish-subscribe, for instance, the additional resources needed for subscription messages are to be included. Generally, this may be traded off with timeliness: greater bandwidth usage/active sessions help in timely delivery of messages. Analysis of these tradeoffs will help understand the pros and cons of a particular interaction paradigm.
\end{itemize}

\subsection{QoS Algebra}

In order to aggregate metrics available from heterogeneous interactions, we make use of an algebraic framework as introduced in \cite{sidney6}. This can handle random variables drawn from  a distribution associated with a lattice domain. A \emph{QoS metric} $q$ is a tuple:
\beq
{q=(\Dom,\leq,\oplus, \bigwedge, \bigvee)}
\label {w0579wth0579}
\eeq
\begin{enumerate}
	\item $(\Dom,\leq)$ is a QoS domain with a corresponding partially ordered set of QoS values. 
	\item $\oplus: \mathbb{D} \times \mathbb{D} \rightarrow \mathbb{D}$ defines how QoS gets incremented by each new \emph{action} or \emph{operation}, like sending a message or receiving an event. It satisfies the following conditions:
	\begin{itemize}
	\item $\oplus$ possesses a \emph{neutral element} $q_0$ satisfying $\forall q \in \mathbb{D} \Rightarrow q \oplus q_0 = q_0 \oplus q = q$.
	\item $\oplus$ is \emph{monotonic}: $q_1 \leq q'_1$ and $q_2 \leq q'_2$ imply $(q_1 \oplus q_2) \leq (q'_1 \oplus q'_2)$.
%	\item Order $\qosleq$ is ``rich enough'': $\forall q,q' \in \mathbb{D}, ~\exists \delta q \in \mathbb{D} ~~\text{such that}~~ q \qosleq q' \qosoplus \delta q$. 
	\end{itemize}
	 \item $(\bigwedge, \bigvee)$ represent the lower and upper lattice, meaning that any $q \subseteq \Dom$ has a unique greatest lower, least upper bound $(\bigwedge_{q}, \bigvee_{q})$. When taking the \emph{best} QoS with respect to the ordering $\leq$, we take the lowest QoS value, with $\bigwedge$.
	When synchronizing actions belonging the the causal past of a same action, the operator $\bigvee$ amounts to taking the \emph{worst} QoS as per the ordering $\leq$.
%	\item $\qoscompet: \mathbb{D} \times {\mathbb{D}}^{*} \rightarrow \mathbb{D}$ is the competition operator that may be applied as choosing the ``best'' choice in many ways: pareto optimal, lexicographic or weighted choice. 	
	\end{enumerate}
%In addition, we make use of the native pruning operator in \orc\ to discard unused QoS tokens according to the semantics of \prunen. 
%
\begin{table}[t]
\vspace{-0.1in}
\begin{center}
{\small
\begin{tabular}{|>{\centering}p{4cm}|>{\centering}p{1.5cm}|>{\centering}p{1.5cm}|>{\centering}p{1.5cm}|>{\centering}p{1.5cm}|>{\centering\arraybackslash}p{1.5cm}|} \hline
QoS Metric & $\Dom$ & $\leq$ & $\oplus$ & $\bigwedge$ & $\bigvee$ \\ \hline
$\delta$:~Timeliness & $\mathbb{R}_{+}$ & $<$ & $+$ & $\min$ & $\max$ ~~\\
$\mathcal{S}$:~Security/Data Integrity & $\mathbf{Q}$ & $>$ & $\bigvee$ & $\max$ &$\min$ ~~\\
$\lambda$:~Resource Efficiency & $\mathbf{Q}$  & $<$ & $+$ &$\min$ & $\max$ ~~\\ \hline
\end{tabular}}
\end{center}
\caption[i76rtfi7]{Basic classes of QoS domains}
\label {0958th59pu}
\vspace{-0.35in}
\end{table}
%
Basic classes of QoS domains are displayed in Table~\ref{0958th59pu} and composed according to rules specified in Eq. \ref{w0579wth0579}. The use of this algebraic framework allows us to reason, in an abstract way, about the behavior of interaction paradigms and their effect on choreography performance. The framework may be invoked by any choreography description language to incorporate QoS composition. It specifies calculation of the QoS increments via the associated algebra with domains $\mathbb{D}$, partial order $\leq$, and operations $(\oplus, \bigvee, \bigwedge)$. In the case of orchestrations, the increments and composition may be managed by the orchestrator itself (for monitoring SLAs, for instance). In the case of choreographies, this has to be done in a distributed manner, with every action being tagged with a QoS increment. 

%An example specification in \emph{python} is shown below: 
%\begin{lstlisting}
%class Timeliness:                         # Timeliness
    %def __init__(self):
        %self.QoS = random.student_t(nu)   # student-t random variable
    %def QoSOplus(self,q2):                # oplus operator 
        %return (self.QoS + q2) 
    %def QoSCompare(self,q2):              # partial order
        %return self.QoS <= q2
    %def QoSInfimum(self,q2):              # infimum operator
        %v = [self.QoS,q2]
        %return v.sort()
    %def QoSSupremum(self,q2):             # supremum operator
        %return max(self.QoS,q2) 
				%
%class Security:                           # Security
    %def __init__(self):            
        %self.QoS = random.uniform(a,b)    # uniform random variable
    %def QoSOplus(self,q2):                # oplus operator
        %return min(self.QoS,q2) 
    %def QoSCompare(self,q2):              # partial order
        %return self.QoS >= q2
    %def QoSInfimum(self,q2):              # infimum operator
        %v = [self.QoS,q2]
        %return v.sort()    
    %def QoSSupremum(self,q2):             # supremum operator
        %return min(self.QoS,q2)    
%\end{lstlisting}

\section{QoS Analysis of Interactions}
\label{kldakljasdfjk}
In order to upgrade choreography interactions with QoS assessment, we equip every \emph{atomic transaction} $\mathcal{T}$ in a client-service, publish-subscribe, or tuple space interaction with a QoS increment; $\mathcal{T}$ represents an end-to-end interaction enabling sending and receiving of data. This produces a tuple of $(\mathcal{T}, q)$ that may be propagated along the choreography. As the choreography does not have a centralized QoS control mechanism, this propagation of tuples can be combined with the algebraic operators to aggregate these increments. 

%\subsection{Model for Latency}
%In order to abstract the general end-to-end connector that incorporates one-way communication for CS, PS, TS schemes, we make use of the following. A \emph{publisher} can \texttt{post} a message with a validity period \emph{lease}; this is procured within the \emph{timeout} period using the \texttt{get} operation (may be locally done) at the receiver side. These semantics follow the end-to-end GA protocol. 
%
%Taking the time-stamps for the one-way message passing as an example of the QoS metrics, we are presented with Fig. \ref{fgedfgdrgfesrg}. The \texttt{post} and \texttt{get} operations are asynchronous and have individual time-stamps. The \texttt{post} operation proceeds with a timer initiated at $t_{p_0}$; once the post operation has been made to an intermediary (network message in the case of CS, broker in the case of PS, tuple space in the case of TS), the lease period $t_{lease}$ commences. Note that the lease period may be set of 0, as in the case of CS requests. Similarly at the receiver side, a timer is initiated at $t_{g_0}$; once the get operation has initiated (may be locally done to open a server queue, for instance), the timeout period $t_{timeout}$ commences. If the \texttt{getreturn} occurs before the timeout period with valid data (not exceeding the lease), then the transaction is successful.
%
%Since the \texttt{post} and the \texttt{get} operations proceed without any causal link, we provide some general conditions for the transaction to occur. The \texttt{get} operation must receive the message within the timeout period. The data from the \texttt{post} operation must be procured before the lease ends. If the transaction is successful, the overall QoS increment is:
%\begin{equation}
%\delta_{success} = t_{g_0} + \delta_{post} + \delta_{getreturn} - \bigwedge(t_{g_0}, t_{p_0})
%\end{equation}
%However, if either the lease or the timeout periods have been reached, the value of the QoS increment reaches the
%failure clause:
%\begin{equation}
%\delta_{failure} = \bigvee(t_{g_0} + \delta_{timeout},~t_{p_0} + \delta_{post} + \delta_{lease}) - \bigwedge(t_{g_0}, t_{p_0})
%\end{equation}
%Referring to Fig. \ref{fgedfgdrgfesrg}, the success condition occurs when there is an overlap between the post and get message time intervals:
%\begin{equation}
%\delta_{success}: \exists\delta \in [t_{g_0} + \delta_{get}, t_{g_0} + \delta_{timeout}] \cap [t_{p_0} + \delta_{post}, t_{p_0} + \delta_{post} + \delta_{lease}]
%\end{equation}
%\begin{figure}[t] 
%\centering
%\includegraphics[height=4cm]{GA_timestamps.eps}
%\caption{Analysis of \texttt{post} and \texttt{get} operations.}
%\label{fgedfgdrgfesrg}
%\vspace{-0.25in}
%\end{figure}

\subsection{QoS Model for Generic XSB Transactions}
\label{sdklfhaskjhklj}

The XSB connector can represent end-to-end transactions for any one of the CS, PS, TS connectors.
Then, one-way interaction for any one of these connectors can be abstracted as follows.   
A sender can \texttt{post} \emph{data} -- representing a \emph{message}, \emph{event} or \emph{tuple} -- with a validity period \texttt{lease}; this is procured within the \texttt{timeout} period using the \texttt{get} operation at the receiver side. The two peers initiate their actions independently.

\subsubsection{Model for Timeliness.}

Fig. \ref{fgedfgdrgfesrg} depicts an one-way XSB transaction as a correlation in time between a \texttt{post} action and a \texttt{get} action.  
The \texttt{post} and \texttt{get} operations are asynchronous and have individual time-stamps.
The \texttt{post} operation is initiated at $t_{post_0}$. At $t_{med}$, the posted data arrive at the intermediary \emph{medium}; we introduce this notion to represent the broker/data space in the case of PS/TS, or the remote CS middleware entity.
A timer is initiated at $t_{med}$, constraining the data availability to the \texttt{lease} period $t_{lease}$.
Note that the \texttt{lease} period may be set to 0, as in the case of CS messages.
Similarly at the receiver side, the \texttt{get} operation is initiated at $t_{get_0}$, together with a timer controlling the \texttt{timeout} period $t_{timeout}$.
If \texttt{get} returns before the \texttt{timeout} period with valid data (not exceeding the \texttt{lease}), then the transaction is successful.
We consider this instance also as the end of the \texttt{post} operation. 
Hence, if the transaction is successful, the overall QoS increment is:
\begin{equation}
%\delta_{success} = \bigvee(\delta_{post},~\delta_{get})
\delta = \bigvee(\delta_{post},~\delta_{get})
\label{sdklgsdjlkjsdkl}
\end{equation}
where $\delta_{post}$ and $\delta_{get}$ represent the durations of the two corresponding actions.
In the case of failure, there is no overlapping in time between the two actions. In other words, only one of them takes place, and goes up to its maximum duration, i.e., $\delta_{med}$ + \texttt{lease} for \texttt{post} or \texttt{timeout} for \texttt{get}, while the other's duration is \texttt{0}. Hence, the QoS output is once again as in Eq. \ref{sdklgsdjlkjsdkl}. 
Finally, we note that, while we present the synchronous data reception case, the case with asynchronous \texttt{get} and callbacks follows similar timeliness composition models.

\begin{figure}[t] 
\vspace{-0.1in}
\centering
\includegraphics[height=4.5cm]{GA_timestamps.eps}
\vspace{-0.1in}
\caption{Analysis of \texttt{post} and \texttt{get} $\delta$ increments for success and failure.}
\label{fgedfgdrgfesrg}
\vspace{-0.1in}
\end{figure}

%Referring to Fig. \ref{fgedfgdrgfesrg}, since the \texttt{post} and the \texttt{get} operations proceed without any causal link, the \texttt{get} operation must receive the message within the timeout period. The data from the \texttt{post} operation must be procured before the lease ends. 


\subsubsection{Model for Security/Data Quality.}
\begin{figure}[t] 
\centering
\includegraphics[height=4.5cm]{GA_sec_eff.eps}
\vspace{-0.1in}
\caption{Analysis of \texttt{post} and \texttt{get} $\mathcal{S}$ and $\lambda$ increments for success and failure.}
\label{fgedfghfwsertgwdrgfesrg}
\vspace{-0.25in}
\end{figure}

In order to model the data security level associated with each transaction, we equip the \emph{data-carrying} \texttt{post} and \texttt{get} operations, depicted in Fig. \ref{fgedfghfwsertgwdrgfesrg}, with a security level. Note that the \texttt{post} operation here refers to the interaction between the sender and what we called above the \emph{medium}, i.e., the PS broker, TS data space, or remote CS middleware entity.
Locally executed actions, such as \texttt{get(msg)} in the case of CS schemes, come equipped with good security levels. In case of TS schemes, as there is a shared channel between peers (unlike the exclusive channel of CS, PS), the security levels are worse than, for example, PS. For a successful transaction, the supremum of the security levels linked with the actions are taken, which means the worst security level among the supported ones:

\begin{equation}
%\mathcal{S}_{success} = \bigvee(\mathcal{S}_{post},~\mathcal{S}_{get})
\mathcal{S} = \bigvee(\mathcal{S}_{post},~\mathcal{S}_{get})
\label{dskjlfhskjlhfkjshk}
\end{equation}
In the case of failure, Eq. \ref{dskjlfhskjlhfkjshk} still holds, with the operation that did not take place carrying a \texttt{null} security level.
Finally, in the case of asynchronous data reception, the security level composition model is similar to the synchronous case presented here.


\subsubsection{Model for Resource Efficiency.}
When measuring resource efficiency, we include the subset of all \emph{networked} primitives related to the \texttt{post} and \texttt{get} operations, as in Fig. \ref{fgedfghfwsertgwdrgfesrg}. In the case of PS, for instance, the subscription level primitives are taken into account. Note that we only consider synchronous data reception in our evaluation; for asynchronous callbacks, resource efficiency can be evaluated in a similar fashion. In case of success, the resultant resource efficiency is:
\begin{equation}
% \lambda_{success} = \lambda_{post} \oplus \lambda_{get}
\lambda = \lambda_{post} \oplus \lambda_{get}
\label{fdkjhksdjhgjkshk}
\end{equation}
%where $\lambda_{get}$ encompasses the resource usage of subscription level messages as well.
In case of failure, Eq. \ref{fdkjhksdjhgjkshk} still holds, with the missing operation contributing a \texttt{null} value to the metric.


\subsection{Upgrading the API}
\label{lkrgjlkdsjlksdjlk}
We append the API arguments of Table \ref{kjbvfnjkghekhxdjvkjh} with \emph{QoS parameters} that may be either self-measured by the peers or aggregated through a third party service. The QoS increments and composition are presented in Table \ref{sdkjfghjskahfjkshklkjlshj}. 
%As the GA connector abstracts multiple interactions,
The \texttt{post} operation is given an initial QoS value \texttt{q\_{post}}. This is, for the example of timeliness, the timestamp $t_{post_0}$ (see Fig. \ref{fgedfgdrgfesrg}), which is then used at the receiver to calculate the final returned output QoS increment.
For a successful \texttt{get\_sync}, the value specified in Eq. \ref{sdklgsdjlkjsdkl} is returned with \texttt{q\_get\_sync}.
% returning $\uparrow \delta_{post} \oplus \bigwedge(\delta_{get},\texttt{timeout})$.
% Operations such as subscriptions, notifications and callbacks are treated as $q_\phi$, that do not affect timeliness and security, but do however add to resource efficiency.
In the case of failure, the resulting timeliness value can be measured either by the receiver (\texttt{timeout}) or by a probe installed at the medium ($\delta_{med}$ + \texttt{lease}). 

	\begin{table}[t]
	\hspace{-0.1in}
	\centering
		{\scriptsize
	\begin{tabular}{|p{2.3cm} | p{9.5cm}|}
	\hline
\textbf{Primitives}&\textbf{Arguments}\\ \hline
	%
	  %Client-Server & 
	%\texttt{send} & \texttt{destination, operation, input, q\_send}\\
	%&\texttt{receive\_sync} & $\uparrow$\texttt{source,} \texttt{operation,} $\uparrow$\texttt{output, timeout, $\uparrow$\texttt{q\_receive\_sync}}\\
	%&\texttt{receive\_async} & \texttt{source,} \texttt{operation,} $\uparrow$\texttt{callback(source, operation, input),} $\uparrow$\texttt{handle}, $\uparrow \texttt{q\_receive\_async}$\\
	%&\texttt{end\_receive\_async} & \texttt{handle}, \texttt{q\_end\_receive\_async}\\ 
	%&\texttt{invoke\_sync} & \texttt{destination, operation, input, q\_send, $\uparrow$output, timeout, 
	%$\uparrow$\texttt{q\_invoke\_sync}}\\
	%&\texttt{invoke\_async} & \texttt{destination, operation, input, q\_send,} $\uparrow$\texttt{callback(output),} $\uparrow$\texttt{handle, $\uparrow \texttt{q\_invoke\_sync}$}\\
	%\hline
		%
	%Publish-Subscribe &	\texttt{publish} & \texttt{broker, filter, event, lease, q\_publish}\\
	%&\texttt{subscribe} & \texttt{broker, $\uparrow$filter, $\uparrow$handle, q\_subscribe}\\
	%&\texttt{get\_next} & \texttt{handle, $\uparrow$event, timeout, $\uparrow$\texttt{q\_get\_next}}\\
	%&\texttt{listen} & \texttt{handle, $\uparrow$callback(event), \texttt{q\_listen}}\\
	%&\texttt{end\_listen} & \texttt{handle, \texttt{q\_end\_listen}}\\
	%&\texttt{unsubscribe} & \texttt{handle, \texttt{q\_unsubscribe}}\\ \hline
	%
	%Tuple Space & \texttt{out} & \texttt{tuple\_space, template, tuple, lease, q\_{out}} \\
	%&\texttt{take} & \texttt{tuple\_space, template, tuple, policy, $\uparrow$tuple, timeout, $\uparrow$q\_take}\\
	%&\texttt{read} & \texttt{tuple\_space, template, tuple, policy, $\uparrow$tuple, timeout, $\uparrow$q\_read}\\
	%&\texttt{register} & \texttt{tuple\_space, template, $\uparrow$callback(), $\uparrow$handle, \texttt{q\_register}}\\
  %&\texttt{unregister} & \texttt{handle, \texttt{q\_unregister}}\\ \hline
		%%
	
\texttt{post} & \texttt{scope, data, q\_{post}}\\
	\texttt{get\_sync}& \texttt{$\uparrow$scope, $\uparrow$data, timeout, $\uparrow$q\_get\_sync}\\
\texttt{get\_async}& \texttt{scope, $\uparrow$callback(scope, data), $\uparrow$handle, $\uparrow$q\_get\_async}\\
\texttt{end\_get\_async}&\texttt{handle, \texttt{q\_end\_get\_async}}\\
\texttt{post\_get\_sync}&\texttt{scope, in\_data, q\_{post}, $\uparrow$out\_data, timeout, $\uparrow$\texttt{q\_post\_get\_sync}}\\
\texttt{post\_get\_async}&\texttt{scope, in\_data, q\_{post}, $\uparrow$callback(out\_data), $\uparrow$handle, $\uparrow$\texttt{q\_post\_get\_async}}\\	\hline

	\end{tabular}}
	\vspace{0.05in}
	\caption{Extending the XSB API for QoS Analysis.}
	\label{sdkjfghjskahfjkshklkjlshj}
	\vspace{-0.35in}
	\end{table}
%\begin{itemize}
	%\item \emph{Client-Server} - We begin with a client appending the input QoS value \texttt{q\_send} to the interaction (such as timestamp $\delta_0$). We distinguish the initial value of the timestamp and the final returned output QoS increment variable through $\uparrow$. A \texttt{receive\_sync} returns the value bound to the output variable $\uparrow$\texttt{q\_receive\_sync} as $\bigwedge(\delta_{receive},~\texttt{timeout})$, where $\delta_{receive}$ is the difference between send and receive timestamps. For two-way \texttt{invoke\_sync}, the output QoS comes tagged with $\uparrow \bigwedge(\delta_{receive_1},\texttt{timeout}) \oplus \bigwedge(\delta_{receive_2},\texttt{timeout})$.	
	%\item \emph{Publish-Subscribe} - Similarly, we append the publish subscribe interactions with QoS increments. Publishers send data to a broker with an initial QoS value \texttt{q\_publish}. Subscription/Listening to a publishing broker is treated as $q_{\phi}$ which may not directly affect the message reception from the publisher. The \texttt{get\_next} reception appends the value \texttt{q\_get\_next} with the increment for $\uparrow \delta_{publish} \oplus \bigwedge(\bigwedge(\delta_{getnext},\texttt{timeout}),\texttt{lease})$, taking care of, both coupled and decoupled QoS increments.  
	%\item \emph{Tuple Space} - Likewise, tuple spaces are equipped with QoS increments. Note that we treat take and read similarly with similar QoS increments $\uparrow \delta_{out} \oplus \bigwedge(\bigwedge(\delta_{take},\texttt{timeout}),\texttt{lease})$. Notification and callbacks are treated with $q_\phi$ as they do not directly affect read/write operations. 
		%
	%\item \emph{GA Converter} -  As the GA connector abstracts multiple interactions, the post operation is given a generic increment $q_{post}$. To distinguish synchronous and asynchronous two-way messaging, the increments returned are $\delta_{post} \oplus \bigwedge(\delta_{get},\texttt{timeout})$ and $\delta_{post} \oplus \delta_{get}$, respectively. Operations such as notification and callbacks are, once again, treated as $q_\phi$.
%\end{itemize}


\subsection{Model for QoS Propagation}

The QoS model for generic XSB transactions and the related API introduced in Sections \ref{sdklfhaskjhklj} and \ref{lkrgjlkdsjlksdjlk} can be applied for measuring QoS in heterogeneous choreographies where CS, PS and TS systems are interconnected via an XSB bus (see Fig. \ref{fig:CHOReOS}).
In particular, the model and API introduced for XSB can be easily transcribed to the corresponding primitives and transactions of CS, PS and TS.
Additionally, they can be used directly for the transactions performed on the XSB bus interconnecting heterogeneous systems.
For multiple sequential choreography transactions, QoS increments can be propagated along with the transaction data and be passed from one transaction to the following one.
Hence, QoS values can be calculated, propagated and aggregated along end-to-end choreography links, such as the ones depicted in Fig. \ref{fig:CHOReOS}.
%As the XSB connector is able to coordinate with various interaction protocols, a natural extension of our technique is to propagate QoS increments along with the message data. The connector has a rich interface, with the QoS increments suitably transformed into the necessary models for interactions.Such general ``QoS equipped'' message passing would allow choreographies to interact with stateless/stateful services, data feeds and sensors/actuator networks.
%As the XSB connector API is rich enough, we merely transform the QoS values produced via CS/TS/PS paradigms as values associated with $q_{post},~q_{get}$. This is realistic as the QoS monitoring from each of the interactions considers the end-to-end response encompassing increments provided by network, middleware and applications. The propagation of these values along the connector (as in Fig. \ref{kdjfbakjsfhfkjskj}) would involve aggregation of three transactions.
For example, in the case of timeliness for an one-way CS-XSB-PS transaction, we need to aggregate the three involved transactions:

\begin{equation}
%\delta_{success} = \bigvee(\delta_{send},~\delta_{receive}) \oplus \bigvee(\delta_{post},~\delta_{get})  \oplus \bigvee(\delta_{publish},~\delta_{getnext})
\delta = \bigvee(\delta_{send},~\delta_{receive}) \oplus \bigvee(\delta_{post},~\delta_{get})  \oplus \bigvee(\delta_{publish},~\delta_{getnext})
\end{equation}
In a similar fashion, for timeliness or other QoS metrics, QoS increments can be composed for both one-way and two-way interaction.

%\begin{itemize}

	

%\item The CS component sends out a request with $q_{req}$ to the GA connector. The response from the PS service comes tagged with $\uparrow q_{post} \oplus  q_{getnext} \oplus q_{pub}$; that from a TS service comes with $\uparrow q_{post} \oplus q_{write} \oplus q_{read}$. These are provided back to the composite service in the CS paradigm with response linked with $\uparrow q_{req} \oplus q_{res}$. This procedure aggregates the increments produced by both the interactions and the associated connectors. Note that we assume here that $q_{timeout}$ and $q_{lease}$ constraints are already met.

	

%\item The PS component sends out a get request with $q_{getnext}$. The response from the CS service comes tagged with $\uparrow q_{post} \oplus  q_{res} \oplus q_{req}$; that from a TS service comes with $\uparrow q_{post} \oplus q_{write} \oplus q_{read}$. These are provided back to the service in the PS paradigm with response linked with $q_{pub}$, a publication to the broker.

	

%\item The TS component sends out a get request with $q_{read}$. The response from the CS service comes tagged with $\uparrow q_{post} \oplus  q_{res} \oplus q_{req}$; that from a PS service comes with $\uparrow q_{post} \oplus  q_{getnext} \oplus q_{pub}$. These are provided back to the tuple in the TS paradigm with response linked with $q_{write}$, writing to the tuple space.
%\end{itemize}



%\begin{figure}[ht]
%\centering
%\includegraphics[height=14cm]{GA.eps}
%\caption{Message Interaction Paradigms with GA connectors.}
%\label{dsddsgdsxfs}
%\end{figure}



%The QoS enhanaced API is presented below with $|$ representing choice between interaction paradigms.
%

	

	

%\begin{table}[ht]

	

%\centering

	

%\begin{tabular}{l | l}

	

%\textbf{Primitives}&\textbf{Arguments}\\

	

%post & coupling\{strong, weak, very weak\},\\

	

%&scope\{source-destination | broker | tuplespace, operation | filter | template\}, data,\\

	

%& $\bot_q$, $q_{req} ~|~ q_{pub} ~|~ q_{write}$\\

	

%set get& coupling, $\rightarrow$ scope, $\rightarrow$ handle, $q_\phi$\\

	

%get syncronous& handle, policy, $\rightarrow$ data, $\bigvee_q$,

	

%$q_{req} \oplus q_{res}~|~(\bigvee q_{pub}) \oplus q_{get}~|~(\bigvee q_{write}) \oplus q_{read}$\\

	

%get asynchronous& handle, $\rightarrow$ data, callback, $(\bigvee q_{req}) \oplus q_{res}~|~(\bigvee q_{pub}) \oplus q_{get}~|~(\bigvee q_{write}) \oplus q_{read}$\\

	

%notify & callback, scope, data, $q_\phi$\\

	

%end get asynchronous&callback, $q_\phi$\\

	

%end set get&handle, $q_\phi$

	

%\end{tabular}

	

%\caption{Tuple Space API.}

	

%\end{table}



%
%\begin{figure}[ht]
%\vspace{-0.1in}
%\centering
%\includegraphics[height=8.5cm]{interaction_QoS.eps}
%\vspace{-0.1in}
%\caption{Message Interaction Paradigms appended with QoS.}
%\label{dfl;jlhgljuioufls}
%\vspace{-0.2in}
%\end{figure}

\section{Results: QoS in Choreography Interactions}
\label{sdkgjlksdjgklsjglsjd}
Choreographies involve heterogeneous interactions between services, things (sensors/actuators), computational entities and human participants. The use of our QoS analysis enables the following:
\begin{enumerate}
	\item \emph{Bottom-up Choreography Designs}: where the interactions are fixed but the choreography enaction and the expected QoS can be modified. The composition models take into account the nature of the interaction and their effect on the composed QoS. This is primarily done at \emph{design-time} with previously collected statistics. 
	\item \emph{Top-down Choreography Designs}: fixed choreography specifications that may be implemented by varied interaction paradigms. At \emph{runtime}, similar functionality may be replicated by services/things in a registry -- leading to late binding. Focusing on QoS, we study the possibility of replacing an interaction with another to prevent deterioration of output QoS. 
\end{enumerate}
For example, an improvement in performance $\delta$  by the interactions is traded off with deteriorating $\lambda$. Thus, if cost of bandwidth is to be taken into consideration, a choice can be made at design time to select a particular interaction paradigm over another. This involves discovering services that are implemented with specific interaction paradigms. In case this is not exposed, the worst case performance for each domain must be expected at design time. At runtime, if re-configuration \cite{reconfig_chor} or replacement/late-binding occurs, changes that may be expected through varied interaction paradigms may be evaluated. For instance, reduced $\mathcal{S}$ may be traded off with improvements in $\delta$. 

\subsection{Comparison of Tradeoffs}

To compare the effect of CS/PS/TS paradigms on QoS metrics such as timeliness, security and message efficiency, simulations were performed according to the models provided in Section \ref{sdklfhaskjhklj}. As any particular implementation is affected by the network load, middleware and individual applications' QoS increments, we assume some general characteristics in our simulations. The interactions are assumed to follow tight space-time coupling for CS/PS/TS to prevent failed transactions (even though our analysis in Section \ref{sdklfhaskjhklj} can handle this). The details for the specific interactions are:
\begin{itemize}
	\item \emph{Client-Service} - At $(t_{post_0})$, every client posts a message to a single server. Two measurements are made: the QoS increments associated with one-way post-get messages; the QoS increments with round-trip two-way request-response invocations. CS assumes tight space-time coupling and that the server is available and connected to the client. The response \texttt{get(msg)} is linked with the end-to-end QoS increments. 
	\item \emph{Publish Subscribe} - At $(t_{post_0})$, a publication to a broker is initiated, which is then forwarded to the peers. We assume that the broker is efficient and that it forwards the messages to all subscribed peers synchronously (\texttt{get\_next}). The broker intermediary adds some latency $\delta_{broker}$ and has some effect on the security level $\mathcal{S}_{broker}$. The subscription level messages \texttt{subscribe}, \texttt{unsubscribe} are considered during message efficiency calculations. While PS schemes typically allow only one-way publisher to subscriber messaging, to compare with the two-way CS case, we assume that the applications may behave as a publisher+subscriber for the two-way interaction.
	\item \emph{Tuple Space} - At $(t_{post_0})$, data is written to a tuple, which may be read by peers. Synchronous write-read scenarios are studied, with the data space being efficient in matching tuples. Note that there may be QoS increments introduced between writing and reading from the tuple, captured by $\delta_{tuplespace}$, $\mathcal{S}_{tuplespace}$. Of particular interest is the data integrity/security of the tuples, as these may be modified/removed by any of the peers. Two-way interaction is additionally studied, with a writer to a tuple later functioning as a reader. 
	\item \emph{XSB} - When converting between these schemes via a common bus protocol provided by the XSB, QoS increments are produced. These are appended for various domains using $\delta_{post}, \mathcal{S}_{get}$ and so on. The conversion also increases the bandwidth resource usage that must be taken into account.
\end{itemize}
Based on \cite{webperf}, the QoS random variables are modeled as follows: $\delta$ as a \emph{heavy-tailed} (\texttt{nctrnd}) distribution; $\mathcal{S}$ as a \emph{uniform} (\texttt{randi}) distribution; $\lambda$ as an \emph{exponential} (\texttt{exprnd}) distribution. The simulations are done in MATLAB with increments and random variables provided as in Table \ref{kljsdglkjasdfjh}. We assume uniform performance of the interactions, with $\delta_{send}$, $\delta_{post}$, $\delta_{pub}$ drawn from distributions with similar mean and variances. Slight variations are provided, with faster response times pertaining to the broker, tuple space and bus protocols. The security level of the tuple space is set to be lower than other interaction paradigms, as the data can be maliciously modified by peers. These values can differ according to the implementations, network load and resource management accorded. 
	\begin{table}[t]
	\vspace{-0.1in}
	\centering
		{\scriptsize
	\begin{tabular}{|p{9cm} |p{2.6cm} |}
	\hline
	{\hspace{1.3in}\textbf{QoS Increments}}&~~~\textbf{MATLAB call}\\ \hline
	$\delta_{send},~\delta_{receive},~\delta_{pub},~\delta_{getnext},~\delta_{out},~\delta_{read}$  &~~~~\texttt{nctrnd(1,10)}\\
	$\delta_{broker},~\delta_{tuplespace},~\delta_{post},~\delta_{get}$  &~~~~\texttt{nctrnd(1,2)}\\
	$\mathcal{S}_{send},~\mathcal{S}_{receive},~\mathcal{S}_{pub},~\mathcal{S}_{getnext},~\mathcal{S}_{out},~\mathcal{S}_{read}, ~\mathcal{S}_{broker},~\mathcal{S}_{post},~\mathcal{S}_{get}$  &~~~~\texttt{randi(3)}\\
	$\mathcal{S}_{tuplespace}$&~~~~\texttt{randi(2)}\\
	$\lambda_{send},~\lambda_{receive},~\lambda_{pub},~\lambda_{getnext},~\lambda_{out},~\lambda_{read},~\lambda_{sub},~\lambda_{endsub},~\lambda_{post},~\lambda_{get}$  &~~~~\texttt{exprnd(5)}\\
		\hline
	\end{tabular}}
	\vspace{0.02in}
	\caption{Simulation Parameters in MATLAB.}
	\label{kljsdglkjasdfjh}
	\vspace{-0.4in}
	\end{table}
	
As shown in Fig. \ref{xzvsdgsdtwe}, there are differences in performance of these schemes for the evaluated QoS metrics. The cases considered were: \emph{one-way interaction}: CS send-receive, PS publish-subscribe, TS write-read; \emph{two-way interaction}: CS invocation, PS publish-subscribe-(re)publish-subscribe, TS write-read-(re)write-read. In case of \emph{timeliness} $\delta$, the one and two-way CS schemes performed superiorly to corresponding TS and PS schemes. For \emph{security} $\mathcal{S}$, as an intermediate broker or data space are employed by the PS/TS schemes, the levels are consistently lower than that of the CS scheme. The security level of the TS scheme is lower than that of the PS scheme due to the ability of peers to access common data. \emph{Message efficiency} $\lambda$ considers individual subscriptions needed by the PS scheme, which increases the number of messages per interaction. 

\begin{figure}[t]
\centering
\includegraphics[height=4.5cm]{1user.eps}
\vspace{-0.1in}
\caption{QoS composition with CS, TS, PS paradigms.}
\label{xzvsdgsdtwe}
\vspace{-0.1in}
\end{figure}

We continue this evaluation in Fig. \ref{xzvsdgsdvxfgfvdwe} with the effect of using the intermediate XSB connectors on these metrics. The increments are studied for two-way interaction across connectors. While there are not significant differences in domains $\delta$ and $\mathcal{S}$ for the CS-PS-TS interconnection, the CS-TS interconnection has lower message efficiency $\lambda$. Having these statistics in mind, it is possible to study the runtime replacement of a particular connection with another, as we see in the next section.

\begin{figure}[t]
\centering
\includegraphics[height=4.5cm]{1userCSTS.eps}
\vspace{-0.1in}
\caption{QoS composition across the XSB connector.}
\label{xzvsdgsdvxfgfvdwe}
\vspace{-0.25in}
\end{figure}
	
\subsection{Substituting Interactions}
In large spaces of services and devices \cite{iot1}, late-binding and replacement procedures are commonly employed. The replacement of heterogeneous systems in such cases should take into account the interaction paradigms and their corresponding QoS. A level of control is to check if the replacement would not affect the particular QoS metric in hand. In order to compare the statistics provided by two interaction paradigms, we employ nonparametric hypothesis tests.

The two-sample \emph{Kolmogorov-Smirnov} test \cite{KS_test} is a nonparametric hypothesis test that evaluates the difference between the cumulative distribution functions of two sample data sets. This test may also be used to test whether two underlying one-dimensional probability distributions differ. In this case, the Kolmogorov-Smirnov statistic is:
\begin{equation}
\mathbf{KS}_{n,n'}=\bigvee_{q} \vert~F_{1,n}({q})-F_{2,n'}({q})~\vert
\end{equation}
where $F_{1,n}$ and $F_{2,n'}$ are the empirical distribution functions of the first and the second sample data sets with $n$ and $n'$ elements in the vectors, respectively. The hypothesis test result is returned as a logical value: $\mathbf{h} = 0$ indicates an acceptance of the null hypothesis at $\alpha$ significance level: that the data in vectors ${q}_1$ and ${q}_2$ are from the same continuous distribution; $\mathbf{h} = 1$ indicates the rejection of the null hypothesis at $\alpha$ significance level: the alternative hypothesis is that ${q}_1$ and ${q}_2$ are from different continuous distributions. The null hypothesis is accepted at level $\alpha$ if:
\begin{equation}
\sqrt{\frac{n n'}{n + n'}}\mathbf{KS}_{n,n'} \leq K_\alpha
\end{equation}
We make use of this test on the observations of the CS, TS, PS schemes when applied to connectors, such as in Fig. \ref{xzvsdgsdvxfgfvdwe}. This is to determine whether a particular scheme can be replaced with another when querying for a particular QoS metric ($\delta, \mathcal{S}, \lambda$). We set this tests in MATLAB with $\alpha = 1\%$ as \texttt{[h,KSstat] = kstest2(q1,q2,0.01)} in Table \ref{dkjsghskjdjghkjswhbdfj}.

\begin{table}[t]
\vspace{-0.1in}
\centering
{\scriptsize
\begin{tabular}{c|c|c|c}
\multicolumn{4}{c}{$\delta$: \textbf{Timeliness}} \\ \hline
Connectors&CS-PS&CS-TS&PS-TS\\\hline
CS-PS&--&\texttt{h = 0;~KSstat = 0.0115}&\texttt{h = 1;~KSstat = 0.0309}\\
CS-TS&\texttt{h = 0;~KSstat = 0.0115}&--&\texttt{h = 1;~KSstat = 0.0240}\\
PS-TS&\texttt{h = 1;~KSstat = 0.0309}&\texttt{h = 1;~KSstat = 0.0240}&--\vspace{0.1in}\\

\multicolumn{4}{c}{$\mathcal{S}$: \textbf{Security}} \\ \hline
Connectors&CS-PS&CS-TS&PS-TS\\\hline
CS-PS&--&\texttt{h = 0;~KSstat = 0.0128}&\texttt{h = 0;~KSstat = 0.0088}\\
CS-TS&\texttt{h = 0;~KSstat = 0.0128}&--&\texttt{h = 0;~KSstat = 0.0216}\\
PS-TS&\texttt{h = 0;~KSstat = 0.0088}&\texttt{h = 0;~KSstat = 0.0216}&--\vspace{0.1in}\\

\multicolumn{4}{c}{$\lambda$: \textbf{Message Efficiency}} \\ \hline
Connectors&CS-PS&CS-TS&PS-TS\\\hline
CS-PS&--&\texttt{h = 1;~KSstat = 0.3335}&\texttt{h = 0;~KSstat = 0.0102}\\
CS-TS&\texttt{h = 1;~KSstat = 0.3335}&--&\texttt{h = 1;~KSstat = 0.3413}\\
PS-TS&\texttt{h = 0;~KSstat = 0.0102}&\texttt{h = 1;~KSstat = 0.3413}&--\vspace{0.1in}\\
\end{tabular}}
\vspace{0.05in}
\caption{KS Tests applied to various connectors.}
\label{dkjsghskjdjghkjswhbdfj}
\vspace{-0.35in}
\end{table}
This provides some interesting insights: assuming certain distributions on the underlying interactions (as in Fig. \ref{xzvsdgsdvxfgfvdwe}), for timeliness $\delta$, the CS-PS interaction can be suitably replaced by the CS-TS interaction; for security $\mathcal{S}$, all interactions are replaceable with the $1\%$ confidence interval selected; for message efficiency $\lambda$, the CS-PS interaction can be suitably replaced by the PS-TS interaction. Though this can change according to measurements and collected statistics, this procedure can be applied in general cases to safely replace interactions. For example, if contractual obligations and SLAs need to be met in certain domains, deterioration of the QoS metrics due to replacement would be deterred. This sort of comparison not only takes into account the probabilistic nature of the QoS metrics, but also the tradeoffs provided due to the multi-dimensional QoS evaluation and corresponding interaction paradigms.

\section{Related Work}
\label{fsdmlkjflksdjk}
QoS issues in web services span multiple topics, such as optimal late-binding (discovery, selection, substitution) and contract management (SLAs, negotiation, monitoring). Such QoS composition techniques are used by Zeng et al. \cite{QoS_composition} for optimal decomposition of global QoS constraints into local constraints for composition in the case of service orchestrations. An algebraic formulation based on multi-dimensional probabilistic models is proposed in \cite{sidney6} to compose QoS metrics in the case of web services orchestrations. This has been used to support optimization problems for decision making in orchestrations \cite{KattepurBJ11}. In our work, we make use of this algebraic framework and provide an extension for the case of heterogeneous choreography QoS composition.

While QoS issues in composite services based on centralized control (orchestrations) has received some attention, the metrics relevant to choreographies are an active area of research. In \cite{QoS_choreography}, Mancioppi et al. provide a structured overview of the possible metrics to be incorporated within choreographies. A generalized stochastic Petri net model is proposed in \cite{GSPN} to compose QoS in choreographies. In \cite{moses}, the MOSES framework is proposed as an efficient and flexible technique for runtime self-adaptation in service oriented systems. Adaptive and self-healing choreographies have been studied with the survey by Leite et al. \cite{chor_adaptation} providing a systematic overview of model, measurement, agent and formal methods driven techniques for adaptation. In \cite{goldman}, Goldman et al. use a linear programming framework to predict the QoS of BPMN based web services choreographies. A constraint based model for QoS dependent choreographies is proposed in \cite{ivanovic}. However, these techniques assume typical client-service interactions for analysis.

With an increasing number of devices being interconnected through the Internet of Things \cite{iot1}, extensions to the standard (client-service interaction based) ESB middleware adapters \cite{esb} are required. In the \choreos project \cite{choreos}\cite{esocc13}, the XSB connector is provided, which incorporates multiple interaction paradigms including PS and TS schemes. In order to extend such middleware with QoS, in \cite{qos_middleware}, metrics are integrated in the middleware architecture for discovery, configuration and deployment analysis. In \cite{pubsub_QoS}, the characteristics of publish-subscribe interactions that are crucial to QoS composition are studied in considerable detail. In \cite{mom_QoS}, the publish-subscribe middleware interaction is upgraded with the \emph{Harmony} overlay messaging to prevent runtime QoS deterioration. Our work builds on heterogeneous interaction paradigms and enhances them with QoS composition rules. While QoS in the typical web services setting is done at the application level, capturing the fine-grained interactions within heterogeneous paradigms provide us with a detailed outlook of QoS aggregation policies. These may be exploited during design-time selection or runtime replacement.

\section{Conclusions}
\label{dfjsudhfiuwshhio}
QoS analysis in choreographies typically considers homogeneous client-service interactions and is performed at the application level. Choreographies of heterogeneous devices, such as those in the Internet of Things, require further fine-grained QoS analysis of underlying interaction paradigms. In this paper, we study the effect of heterogeneous middleware connectors, interconnected via the \emph{extensible service bus} from the \choreos project, on choreography QoS metrics. Using multi-dimensional, probabilistic QoS metrics and an algebraic model for composition, this procedure reveals some interesting results. The tradeoffs in particular QoS domains may be studied along with interactions, for efficient selection during design-time. Through hypothesis tests, such as Kolmogorov-Smirnov, runtime replacement of a particular interaction paradigm with another can be performed. In future, we would like to apply these analysis techniques on real-world implementations of large scale heterogeneous choreographies.
{
\bibliographystyle{abbrv}
\bibliography{icsoc_nikolaos}
}

%\begin{thebibliography}{4}
%
%\bibitem{jour} Smith, T.F., Waterman, M.S.: Identification of Common Molecular
%Subsequences. J. Mol. Biol. 147, 195--197 (1981)
%
%\bibitem{lncschap} May, P., Ehrlich, H.C., Steinke, T.: ZIB Structure Prediction Pipeline:
%Composing a Complex Biological Workflow through Web Services. In: Nagel,
%W.E., Walter, W.V., Lehner, W. (eds.) Euro-Par 2006. LNCS, vol. 4128,
%pp. 1148--1158. Springer, Heidelberg (2006)
%
%\bibitem{book} Foster, I., Kesselman, C.: The Grid: Blueprint for a New Computing
%Infrastructure. Morgan Kaufmann, San Francisco (1999)
%
%\bibitem{proceeding1} Czajkowski, K., Fitzgerald, S., Foster, I., Kesselman, C.: Grid
%Information Services for Distributed Resource Sharing. In: 10th IEEE
%International Symposium on High Performance Distributed Computing, pp.
%181--184. IEEE Press, New York (2001)
%
%\bibitem{proceeding2} Foster, I., Kesselman, C., Nick, J., Tuecke, S.: The Physiology of the
%Grid: an Open Grid Services Architecture for Distributed Systems
%Integration. Technical report, Global Grid Forum (2002)
%
%\bibitem{url} National Center for Biotechnology Information, \url{http://www.ncbi.nlm.nih.gov}
%
%\end{thebibliography}


\end{document}
